// 91.解码方法
package Leetcode_Second_Brush;

public class Solution091 {
    public int numDecodings(String s) {
        // 剪枝，若字符串以 '0' 开头则无法解码
        if (s.charAt(0) == '0')
            return 0;

        int length = s.length();

        // dp[i] 表示以 s[i] 结尾字符串编码的数量
        int[] dp = new int[length + 1];

        // 初始化
        dp[0] = 1; // dp[0] 表示空字符串的解码方式数量
        dp[1] = 1; // dp[1] 表示第一个字符的解码方式数量

        for (int i = 2; i <= length; i++) {
            char current = s.charAt(i - 1);
            char previous = s.charAt(i - 2);

            // 检查当前字符是否可以单独解码
            if (current != '0') {
                dp[i] += dp[i - 1];
            }

            // 检查当前字符和前一个字符是否可以组合解码
            if (previous == '1' || (previous == '2' && current <= '6')) {
                dp[i] += dp[i - 2];
            }

            // 剪枝，如果出现不能解码的情况
            if (dp[i] == 0)
                return 0;
        }

        return dp[length];
    }

}
